/**
 * //Given an array of integers heights representing the histogram's bar height
 * //where the width of each bar is 1, return the area of the largest rectangle in the
 * //histogram.
 * //
 * //
 * // Example 1:
 * //
 * //
 * //Input: heights = [2,1,5,6,2,3]
 * //Output: 10
 * //Explanation: The above is a histogram where width of each bar is 1.
 * //The largest rectangle is shown in the red area, which has an area = 10 units.
 * //
 * //
 * // Example 2:
 * //
 * //
 * //Input: heights = [2,4]
 * //Output: 4
 * //
 * //
 * //
 * // Constraints:
 * //
 * //
 * // 1 <= heights.length <= 10⁵
 * // 0 <= heights[i] <= 10⁴
 * //
 * //
 * // Related Topics 栈 数组 单调栈 👍 2203 👎 0
 */

package com.xixi.dataStructure.stack;

import java.util.Stack;

public class ID00084LargestRectangleInHistogram {
    public static void main(String[] args) {
        Solution solution = new ID00084LargestRectangleInHistogram().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int largestRectangleArea(int[] heights) {

            int len = heights.length;
            if (len == 1) return heights[0];

            Stack<Integer> indexStack = new Stack<>(); //stack grows up higher and higher
//        indexStack.push(-1); //sentry node
            int res = 0;


            for (int i = 0; i < len; i++) { //traverse every column from left to right
                //when meet a column lower than stack top
                while (!indexStack.isEmpty() && heights[i] < heights[indexStack.peek()]) { //from right pop the index in order to count the width from right to left

                    int height = heights[indexStack.pop()];
                    while (!indexStack.isEmpty() && height == heights[indexStack.peek()]) { //pop out every equal height column until reach height(left - 1) lower than height[peek];
                        indexStack.pop();
                    }
                    int width;
                    if (indexStack.isEmpty()) {
                        width = i;
                    } else {
                        width = i - indexStack.peek() - 1;
                    }

                    res = Math.max(res, height * width);

                }
                indexStack.push(i);

            }

            while (!indexStack.isEmpty()) {
                int height = heights[indexStack.pop()];

                while (!indexStack.isEmpty() && height == heights[indexStack.peek()]) { //pop out every equal height column until reach height(left - 1) lower than height[peek];
                    indexStack.pop();
                }
                int width;
                if (indexStack.isEmpty()) {
                    width = len;
                } else {
                    width = len - indexStack.peek() - 1;
                }
                res = Math.max(res, height * width);
            }


            return res;


        }


    }
//leetcode submit region end(Prohibit modification and deletion)


}